package common
//一致性hash算法
import (
	"errors"
	"hash/crc32"
	"sort"
	"strconv"
	"sync"
)

type units []uint32

var errEmpty = errors.New("hash环没有数据")

//保存hash信息的结构体
type Consistent struct {
	//hash环
	circle map[uint32]string
	//排序节点切片
	sortedHashes units
	//虚拟节点个数
	VirtualNode int
	//读写锁
	sync.RWMutex
}

func NewConsistent() *Consistent {
	return &Consistent{
		circle: make(map[uint32]string),
		VirtualNode: 20,
	}
}

//生成key
func (c *Consistent) generateKey(element string, index int) string {
	return element + strconv.Itoa(index)
}

//获取hash位置
func (c *Consistent) hashkey(key string) uint32 {
	if len(key) < 64 {
		var tmp [64]byte
		copy(tmp[:], key)
		return crc32.ChecksumIEEE(tmp[:len(key)])
	}
	return crc32.ChecksumIEEE([]byte(key))
}

func (c *Consistent) updateSortedHashes() {
	hashs := c.sortedHashes[:0]
	//切片容量如果过大，重置
	if cap(c.sortedHashes) / (c.VirtualNode * 4) > len(c.circle) {
		hashs = nil
	}

	//添加hashs
	for k := range c.circle {
		hashs = append(hashs, k)
	}

	//对hash值进行排序
	sort.Sort(hashs)
	c.sortedHashes = hashs
}

func (c *Consistent) Add(element string) {
	c.Lock()
	defer c.Unlock()
	c.add(element)
}

//添加节点
func (c *Consistent) add(element string) {
	for i := 0; i < c.VirtualNode; i++ {
		c.circle[c.hashkey(c.generateKey(element,i))] = element
	}
	c.updateSortedHashes()
}

func (c *Consistent) Remove(element string) {
	c.Lock()
	defer c.Unlock()
	c.remove(element)
}

//删除节点
func (c *Consistent) remove(element string) {
	for i := 0; i < c.VirtualNode; i++ {
		delete(c.circle, c.hashkey(c.generateKey(element, i)))
	}
	c.updateSortedHashes()
}

func (c *Consistent) search(key uint32) int {
	f := func(x int) bool {
		return c.sortedHashes[x] > key
	}
	//二分查找
	i := sort.Search(len(c.sortedHashes), f)
	if i > len(c.sortedHashes) {
		return 0
	}
	return i
}

func (c *Consistent) Get(name string) (string, error) {
	c.RLock()
	defer c.Unlock()
	if len(c.circle) == 0 {
		return "", errEmpty
	}

	//计算hash
	key := c.hashkey(name)
	i := c.search(key)
	return c.circle[c.sortedHashes[i]], nil
}

func (x units) Len() int {
	return len(x)
}

func (x units) Less(i,j int) bool {
	return x[i] < x[j]
}

func (x units) Swap(i, j int) {
	x[i],x[j] = x[j],x[i]
}

